Personal recommendations and word-of-mouth advertising can greatly influence an individual's purchase decision. Generally, a consumer is more likely to purchase a product or service based on referral from someone they know and/or trust than based on an independent advertisement. With the arrival of online communication services, such as email, blogs, microblogging services, social networking services, and electronic commerce sites, personal recommendations and word-of-mouth advertising proliferate in an online fashion. Providing incentives to recommending users and to those users who consume recommendations (e.g., shop and/or purchase on the basis of such recommendations) can amplify the effect of such advertising. However, fairly yet effectively incentivizing the participants in such advertising (e.g., recommending and recommended users) to encourage recommendations is a challenging problem.